#include <iostream>
using namespace std;
int f(int n){
	if (n==1)
	return 1;
	if (n==2)
	return 1;
	return f(n-1)+f(n-2);    //时间复杂度 O(2^n)
}

int main(){
	cout << "请输入n: ";
	int i = 0;
	cin >> i;
	cout << "result: " << f(i) << endl; //时间复杂度 O(1)
	return 0;
}